package com.blackholemax.algorithm.search;

import java.util.*;

/**
 * 广度优先搜索（BFS）实现前缀自动补全
 * 与 DFS 区别：用队列代替递归，逐层收集单词
 */
public class TrieBFS {

    /* ---------- 节点定义 ---------- */
    private static class Node {
        boolean isEnd;                          // 是否为一个单词结尾
        TreeMap<Character, Node> children = new TreeMap<>(); // 保证单层字典序
    }

    private final Node root = new Node();

    /* ---------- 插入 ---------- */
    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            cur = cur.children.computeIfAbsent(c, k -> new Node());
        }
        cur.isEnd = true;
    }

    /* ---------- 前缀搜索入口 ---------- */
    public List<String> search(String prefix) {
        List<String> ans = new ArrayList<>();
        Node start = findNode(prefix);          // 找到前缀最后一个字符节点
        if (start == null) return ans;          // 前缀不存在

        /* BFS 核心：队列存 (节点, 当前路径) */
        Queue<Pair<Node, String>> queue = new ArrayDeque<>();
        if (start.isEnd) ans.add(prefix);       // 前缀本身是一个单词
        for (Map.Entry<Character, Node> e : start.children.entrySet()) {
            queue.offer(new Pair<>(e.getValue(), prefix + e.getKey()));
        }

        while (!queue.isEmpty()) {
            Pair<Node, String> p = queue.poll();
            Node node = p.key;
            String path = p.value;

            if (node.isEnd) ans.add(path);      // 收集完整单词
            for (Map.Entry<Character, Node> e : node.children.entrySet()) {
                queue.offer(new Pair<>(e.getValue(), path + e.getKey()));
            }
        }
        return ans;
    }

    /* ---------- 辅助：找到前缀终点节点 ---------- */
    private Node findNode(String prefix) {
        Node cur = root;
        for (char c : prefix.toCharArray()) {
            cur = cur.children.get(c);
            if (cur == null) return null;
        }
        return cur;
    }

    /* ---------- 简单 Pair 工具类 ---------- */
    private static class Pair<K, V> {
        K key; V value;
        Pair(K k, V v) { key = k; value = v; }
    }

    /* ---------- 演示 ---------- */
    public static void main(String[] args) {
        TrieBFS trie = new TrieBFS();
        trie.insert("app");
        trie.insert("apple");
        trie.insert("apply");
        trie.insert("apt");
        trie.insert("ape");

        System.out.println(trie.search("ap")); // [app, apple, apply, apt, ape]
        System.out.println(trie.search("app")); // [app, apple, apply]
        System.out.println(trie.search("b"));   // []
    }
}